package com.dysoft.flesh.util;

import java.awt.*;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;

/**
 * @author Sean Micklethwaite
 *         Oct 26, 2010 2:05:05 PM
 *
 * A storage mechanism for 2D shapes, allowing efficient queries for
 * selecting objects in a rectangular region.
 */
public class QuadTree<T> {
	public class Node {
		final Rectangle2D rect;
		final Collection<Entry> objects = new LinkedList<Entry>();

		Collection<Node> children = new ArrayList<Node>();

		public Node(Rectangle2D rect) {
			this.rect = rect;
		}

		public Entry insert(T object, Shape shape, Rectangle2D bounds) {
			if(children.isEmpty()) {
				// Create children (clockwise, from top-left)
				double x = rect.getX(), y = rect.getY(),
					w = rect.getWidth() / 2, h = rect.getHeight() / 2;
				double cx = x + w, cy = y + h;

				children.add(new Node(new Rectangle2D.Double(x, y, w, h)));
				children.add(new Node(new Rectangle2D.Double(cx, y, w, h)));
				children.add(new Node(new Rectangle2D.Double(cx, cy, w, h)));
				children.add(new Node(new Rectangle2D.Double(x, cy, w, h)));
			}


			for (Node n : children) {
				if (n.rect.contains(bounds)) {
					return n.insert(object, shape, bounds);
				}
			}

			//System.out.println("Inserting: " + shape + " in " + rect);
			Entry entry = new Entry(object, shape);
			objects.add(entry);
			return entry;
		}

		public void query(Rectangle2D rect, Collection<? super T> results) {
			for (Entry e : objects) {
				if(e.shape.intersects(rect)) {
					results.add(e.object);
				}
			}
			for (Node n : children) {
				if (n.rect.intersects(rect)) {
					n.query(rect, results);
				}
			}
		}

		public void query(Point2D point, Collection<? super T> results) {
			for (Entry e : objects) {
				if(e.shape.contains(point)) {
					results.add(e.object);
				}
			}
			for (Node n : children) {
				if (n.rect.contains(point)) {
					n.query(rect, results);
					break;
				}
			}
		}

		public class Entry {
			final T object;
			Shape shape;

			public Entry(T object, Shape shape) {
				this.object = object;
				this.shape = shape;
			}

			public Entry update(Shape shape) {
				remove();
				return QuadTree.this.insert(object, shape);
			}

			public void remove() {
				objects.remove(this);
			}

			public Shape getShape() {
				return shape;
			}
		}
	}

	final Node root;

	public QuadTree(Rectangle2D bounds) {
		root = new Node((Rectangle2D)bounds.clone());
	}

	public Node.Entry insert(T object, Shape shape) {
		return root.insert(object, shape, shape.getBounds2D());
	}

	public void query(Rectangle2D rect, Collection<? super T> results) {
		root.query(rect, results);
	}

	public void query(Point2D point, Collection<? super T> results) {
		root.query(point, results);
	}
}
